#include"BinaryTree.h"
BTree* BuyNode(BinaryTreeData x)
{
	BTree* newnode = (BTree*)malloc(sizeof(BTree));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->val = x;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}
void DestoryBTree(BTree* root)
{
	if (root == NULL)
		return;
	DestoryBTree(root->left);
	DestoryBTree(root->right);
	free(root);
}
int BinaryTreeSize(BTree* root)
{
	return root == NULL ? 0 :
		BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
int BinaryTreeLeafSize(BTree* root)
{
	if (root == NULL)
		return 0;
	return root->left == NULL && root->right == NULL ? 1 :
		BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
int BinaryTreeLevelKSize(BTree* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->left,k-1)
		+ BinaryTreeLevelKSize(root->right,k-1);
}
BTree* BinaryTreeFind(BTree* root, BinaryTreeData x)
{
	if (root == NULL)
		return NULL;
	if (root->val == x)
		return root;
	BTree* left = BinaryTreeFind(root->left, x);
	if (left)
		return left;
	BTree* right = BinaryTreeFind(root->right, x);
	if (right)
		return right;
	return NULL;
}
void BinaryTreePrevOrder(BTree* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->val);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}
void BinaryTreeInOrder(BTree* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%d ", root->val);
	BinaryTreeInOrder(root->right);
}
void BinaryTreePostOrder(BTree* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%d ", root->val);
}
int BinaryTreeHeight(BTree* root)
{
	if (root == NULL)
		return 0;
	int LeftHeight = BinaryTreeHeight(root->left);
	int RightHeight = BinaryTreeHeight(root->right);
	return LeftHeight > RightHeight ?
		LeftHeight + 1 :
		RightHeight + 1;
}